package com.xzz.treeBST;

import java.util.HashMap;

/**
 * @author: hhz
 * @create: 2021-12-21 13:59
 * 1373. 二叉搜索子树的最大键值和
 * 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
 * <p>
 * 二叉搜索树的定义如下：
 * <p>
 * 任意节点的左子树中的键值都 小于 此节点的键值。
 * 任意节点的右子树中的键值都 大于 此节点的键值。
 * 任意节点的左子树和右子树都是二叉搜索树。
 **/
public class MaxSumBST {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(2);
        TreeNode node7 = new TreeNode(5);
        TreeNode node8 = new TreeNode(4);
        TreeNode node9 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node7.left = node8;
        node7.right = node9;
        long start = System.nanoTime();
        System.out.println(maxSumBST(node1));
        System.out.println("时间：" + (System.nanoTime() - start) + "ns");

        TreeNode n1 = new TreeNode(-4);
        TreeNode n2 = new TreeNode(-2);
        TreeNode n3 = new TreeNode(-5);
        n1.left = n2;
        n1.right = n3;
        long start1 = System.nanoTime();
        System.out.println(maxSumBST(n1));
        System.out.println("时间：" + (System.nanoTime() - start1) + "ns");

        TreeNode no1 = new TreeNode(1);
        TreeNode no2 = new TreeNode(10);
        TreeNode no3 = new TreeNode(-5);
        TreeNode no4 = new TreeNode(20);
        no1.right = no2;
        no2.left = no3;
        no2.right = no4;
        long start2 = System.currentTimeMillis();
        System.out.println(maxSumBST(no1));
        System.out.println("时间：" + (System.nanoTime() - start2) + "ns");
    }

    static int maxSum = 0;
    static HashMap<TreeNode, Boolean> hashMap = new HashMap<>();

    public static int maxSumBST(TreeNode root) {
        //空的子树也是BST，二空树的键值之和为0
        maxSum = 0;
//        hashMap = new HashMap<>();
//        maxSum(root);
        traverse(root);
        return maxSum;
    }

    //res[0] 记录以 root 为根的二叉树是否是 BST，若为 1 则说明是 BST，若为 0 则说明不是 BST；
    //res[1] 记录以 root 为根的二叉树所有节点中的最小值；
    //res[2] 记录以 root 为根的二叉树所有节点中的最大值；
    //res[3] 记录以 root 为根的二叉树所有节点值之和。
    public static int[] traverse(TreeNode root) {
        // base case
        if (root == null) {
            return new int[]{
                    1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0
            };
        }
        int[] res = new int[4];
        // 递归计算左右子树
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);
        //左右子树为BST 且 root节点的val> 左子树最大的值 <右子树最小的值
        if (left[0] == 1 && right[0] == 1 && left[2] < root.val && right[1] > root.val) {
            res[0] = 1;
            res[1] = Math.min(left[1], root.val);
            res[2] = Math.max(right[2], root.val);
            res[3] = left[3]+right[3]+root.val;
            maxSum = Math.max(res[3],maxSum);
        }else {
            res[0]=0;
        }
        return res;
    }

    //以下做法 ------超出时间限制。。。
    public static void maxSum(TreeNode root) {
        if (root == null) {
            return;
        }

        maxSum(root.left);
        maxSum(root.right);
        boolean leftIsValidBST = false;
        boolean rightIsValidBST = false;
        boolean rootIsValidBST = false;
        //后序遍历代码
        //1、左右子树是否是 BST。
        if (hashMap.get(root.left) == null) {
            leftIsValidBST = isValidBST(root.left);
            hashMap.put(root.left, leftIsValidBST);
        } else {
            leftIsValidBST = hashMap.get(root.left);
        }

        if (hashMap.get(root.right) == null) {
            rightIsValidBST = isValidBST(root.right);
            hashMap.put(root.right, rightIsValidBST);
        } else {
            rightIsValidBST = hashMap.get(root.right);
        }
        if (hashMap.get(root) == null) {
            rootIsValidBST = isValidBST(root);
            hashMap.put(root, rootIsValidBST);
        }
//        //后序遍历代码
//        //1、左右子树是否是 BST。
//        boolean leftIsValidBST = isValidBST(root.left);
//        boolean rightIsValidBST = isValidBST(root.right);
        //2、加上root是不是BST
//        boolean rootIsValidBST = isValidBST(root);


        if (leftIsValidBST && rightIsValidBST && rootIsValidBST) {
            int sum = getSum(root);
            if (sum < 0) {
                maxSum = Math.max(0, maxSum);
            } else {
                maxSum = Math.max(sum, maxSum);
            }

        }

    }

    public static boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
    }

    /* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
    public static boolean isValid(TreeNode root, TreeNode max, TreeNode min) {
        if (root == null) {
            return true;
        }
        if (max != null && root.val >= max.val) {
            return false;
        }
        if (min != null && root.val <= min.val) {
            return false;
        }
        boolean valid = isValid(root.left, root, min);
        boolean valid1 = isValid(root.right, max, root);
        return valid && valid1;
    }

    //获取最小的
    public static TreeNode getMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    //获取最大的
    public static TreeNode getMax(TreeNode root) {
        while (root.right != null) {
            root = root.right;
        }
        return root;
    }

    //获取节点和
    static int sum = 0;

    public static int getSum(TreeNode root) {
        sum = 0;
        getTempSum(root);
        return sum;
    }

    public static void getTempSum(TreeNode root) {
        if (root == null) {
            return;
        }
        getTempSum(root.left);
        getTempSum(root.right);
        sum += root.val;
    }


}
